package com.datastructure.test.findoncenumberinarray;

import java.util.*;

public class FindOnceNumberInArray {

    public static void main(String[] args) {
        FindOnceNumberInArray findOnceNumberInArray = new FindOnceNumberInArray();
        int[] data = {2,2,1};
        int i = findOnceNumberInArray.foundOnceNumber(data, 2);
        System.out.println(i);
    }

    public int singleNumber (int[] nums) {
        // write code here
        int length = nums.length;
        if(length==1){
            return nums[0];
        }
        Arrays.sort(nums);
        int i = 0;
        while ((i+1)<length){
            if(nums[i]!=nums[i+1]){
                return nums[i];
            }else {
                i+=3;
            }
        }
        if(length>=4&&nums[length-1]!=nums[length-2]){
            return nums[length-1];
        }
        return -1;
    }

    public int foundOnceNumber (int[] arr, int k) {
        // write code here
        int length = arr.length;
        if(length==1){
            return arr[0];
        }
        if(arr.length<(k+1)){
            return -1;
        }
        Arrays.sort(arr);
        for (int i = 0; i < length; i++) {
            if(i+1<length-1){
                if(arr[i]!=arr[i+1]){
                    return arr[i];
                } else {
                    i+=(k-1);
                }
            }
        }
        if(length>=(k+1)&&arr[length-1]!=arr[length-2]){
            return arr[length-1];
        }
        return -1;
    }

    public boolean findAppearTwice(int[] arr){
        Arrays.sort(arr);
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]==arr[i+1]){
                return true;
            }
        }
        return false;
    }

    public void moveArray(int[] arr){
        int time = arr.length-1;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==0){
                int j = i;
                for (int k = 0; k < time; k++,j++) {
                    swap(arr,j,j+1);
                }
            } else {
                time--;
            }
        }
    }

    private void swap(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public ArrayList<Integer> cross(int[] data1,int[] data2){
        ArrayList<Integer> result = new ArrayList<>();
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int i : data1) {
            set1.add(i);
        }
        for (int i : data2) {
            set2.add(i);
        }
        for (Integer integer : set1) {
            if(set2.contains(integer)){
                result.add(integer);
            }
        }
        return result;
    }

    public int insertSort(int[] arr){
        if(arr==null){
            return -1;
        }
        if(arr.length==1){
            return arr[0];
        }
        for (int i = 1; i < arr.length; i++) {
            int index = i-1;
            int value = arr[i];
            while (index>=0&&value<arr[index]){
                arr[index+1]=arr[index];
                index--;
            }
            if(index+1!=i){
                arr[index+1]=value;
            }
        }
        return arr[arr.length-1];
    }

    public int quickSort(int[] arr,int left,int right){
        if(left<right){
            int mid = findIndex(arr,left,right);
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }
        return arr[arr.length-1];
    }

    private int findIndex(int[] arr, int left, int right) {
        int index = left;
        int oldValue = arr[left];
        while (left<right){
            while (right>=0&&arr[right]>=oldValue){
                right--;
            }
            while (left<=right&&arr[left]<=oldValue){
                left++;
            }
            if(left<right){
                swap(arr,left,right);
            }
        }
        if(left==right){
            arr[index]=arr[left];
            arr[left]=oldValue;
        }
        return left;
    }
}
